package leetcode;

import java.util.*;

public class LeetCodeMain122 {
    List<String> result=new ArrayList<>();
    public List<String> removeInvalidParentheses(String s) {
        char[] chars=s.toCharArray();
        DFS(chars,0);
        int maxLen = 0;
        for(String str : result)
            maxLen = Math.max(maxLen, str.length());
        List<String> ans = new ArrayList<>();
        for(String str : result)
            if(str.length() == maxLen)
                ans.add(str);
        return ans;
    }
    public void DFS(char[] chars,int startIndex){
        if (isValid(chars)&&!result.contains(toStr(chars))){
            result.add(toStr(chars));
            return;
        }
        for (int i = startIndex; i < chars.length; i++) {
            if (chars[i]=='@'||Character.isLetter(chars[i])){
                continue;
            }
            char ch=chars[i];
            chars[i]='@';
            DFS(chars,i+1);
            chars[i]=ch;
        }
    }
    private String toStr(char[] chars) {
        StringBuilder sb = new StringBuilder();
        for(char ch : chars)
            if(ch != '@')
                sb.append(ch);
        return sb.toString();
    }
    private boolean isValid(char[] chars) {
        Stack<Character> stack = new Stack<>();
        for (char ch:chars) {
            if (ch=='@'||Character.isLetter(ch)){
                continue;
            }
            if (ch=='('){
                stack.push(ch);
            }else if (ch==')'){
                if(stack.isEmpty())
                    return false;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }


    public ListNode mergeKLists(ListNode[] lists) {
        if (lists==null||lists.length==0){
            return null;
        }
        ListNode n1=new ListNode(-1);
        ListNode n2=n1;
        PriorityQueue<ListNode> queue=new PriorityQueue<>((o1, o2) -> o1.val-o2.val);
        for (int i = 0; i < lists.length; i++) {
            if (lists[i]==null){
                continue;
            }
            queue.offer(lists[i]);
        }
        while (!queue.isEmpty()){
            ListNode node=queue.poll();
            n2.next=node;
            if (node.next!=null){
                queue.offer(node.next);
            }
            n2=n2.next;
        }
        n2.next=null;
        return n1.next;
    }
    public ListNode sortList(ListNode head) {
        PriorityQueue<ListNode> queue=new PriorityQueue<>((o1, o2) -> o1.val-o2.val);
        while (head!=null){
            queue.offer(head);
            head=head.next;
        }
        ListNode n1=new ListNode(-1);
        ListNode n2=n1;
        while (!queue.isEmpty()){
            n2.next=queue.poll();
            n2=n2.next;
        }
        n2.next=null;
        return n1.next;
    }
    List<List<Integer>> res=new ArrayList<>();
    List<Integer> list=new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        back(nums,0);
        return res;
    }
    public void back(int[] nums,int startIndex){
        if (list!=null){
            res.add(new ArrayList<>());
        }
        for (int i = startIndex; i < nums.length; i++) {
            list.add(nums[i]);
            back(nums,i+1);
            list.remove(list.size()-1);
        }
    }
    public int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == -1) {
            return Integer.MAX_VALUE;
        }
        if (a==0){
            return 0;
        }
        if (b==1){
            return a;
        }
        if (b==-1){
            return -a;
        }
        boolean flag=a>0&&b>0||a<0&&b<0;
        long a1= Math.abs((long)a);
        long b2= Math.abs((long)b);
        return flag?num(a1,b2):-num(a1,b2);
    }
    public int num(long a,long b){
        if (b>a){
            return 0;
        }
        long tempB=b;
        int count=1;
        while (b+b<a){
            count+=count;
            b+=b;
        }
        return count+num(a-b,tempB);
    }
    public boolean isPalindrome(ListNode head) {
        if (head==null||head.next==null){
            return true;
        }
        ListNode fast=head;
        ListNode slow=head;
        while (fast.next!=null){
            slow=slow.next;
            if (fast.next.next==null){
                fast=fast.next;
            }else {
                fast=fast.next.next;
            }
        }
        ListNode n1=slow.next;
        while (n1!=null){
            ListNode n2=n1.next;
            n1.next=slow;
            slow=n1;
            n1=n2;
        }
        while (head!=fast&&head.next!=fast){
            if (head.val!=fast.val){
                return false;
            }
            head=head.next;
            fast=fast.next;
        }
        if (fast.val!=head.val){
            return false;
        }
        return true;
    }
}
